CCCF专栏 | 孙贤和：量子计算五人谈
量子计算是一个大家都很感兴趣的课题，也是一个在快速发展中的课题。2019新年假期期间，美国的一些学者在线上线下进行了关于量子计算的热烈讨论。我们邀请了孙贤和教授把他们的相关讨论进行了整理，在这里发表，以飨读者。
S：Sun
Y：Yu
W：Wang
Q：Qiang
X：Xu
近期的量子计算方向
S：@Y， 最近到华盛顿开会，听说你们申请到了一个量子计算的大项目，很为你们高兴。
Y：@S，是的。我们最近刚申请到美国政府的一个做量子计算的大项目。美国政府最近推出了一个开展量子计算和量子通信的国家计划[1]，我们这个项目是其中的一部分。
S：@Y，国内关于量子计算和量子通信的报道和讨论特别多，有些离现实比较远。这是我2017年夏天访问美国洛斯·阿拉莫斯国家实验室(Los Alamos National Laboratory)之后写的一个关于量子计算机的解释（见附件“最简量子计算介绍”）。请你看一看，提提意见，也请谈一谈最新的进展。
S：请注意，我在这个量子计算的简介中提到要实现Shor算法(Shor’s algorithm)[2]来分解一个大整数，如2048比特的整数，粗略估算需要4000个逻辑量子比特和2亿个物理量子比特，这显然是短期内无法实现的工程目标。那近期量子计算的研究目标是什么呢？
Y：孙老师的“最简量子计算介绍”内容准确。但是从那时起量子计算又有了一些新的发展。为方便起见，我先简单介绍一下Shor算法。Shor算法是1994年麻省理工学院计算机学家彼得·肖尔(Peter Shor)1 提出的一种用量子计算机进行整数质因数分解的方法。它与已知的经典算法相比有指数级别的加速，而质因数分解本身也是广泛使用的RSA密码协议的基础，所以Shor算法可以对现有的公钥密码造成威胁。Shor算法主要利用了量子叠加态的“并行性”去分解质因数。基于量子计算机制造的现实情况，我们承认实现Shor算法确实短期内难以达到。同时我们也知道抗Shor算法攻击的基于Learning With Errors (LWE)[3]问题的后量子密码体系正在建立。通过Shor算法以达到 “量子霸权”(quantum computational supremacy)不是现阶段量子计算研究的主要目标。近期量子计算研究的一个主要目标是采用基于抽样的方法首次在50~100个左右物理比特的“量子计算机”上通过实验来展示经典计算机不能够完成的计算任务。也就是说，我们要在近期可以实现的量子计算设备上演示量子霸权。第二个目标是实现最近提出的一些量子-经典混合策略的实用算法，用以解决一些实际问题，比如量子化学模拟，解决机器学习问题，达到一定程度的商用价值。现在面临的主要技术难点是量子比特的相干时间过短，以及量子电路里的噪声。加州理工学院的物理学家约翰·普瑞斯基尔(John Preskill)教授把现今处于的技术阶段称为含噪中尺度量子系统(Noisy Intermediate-Scale Quantum, NISQ)阶段[4]。
S： @Y，你说的第二个目标是可行的，也就是我们说的，以一种加速器的形式出现。
Y：是的，现在考虑的计算模式就是让量子芯片像GPU一样，作为加速器和协处理器来使用。
如何在现有的量子计算机上实现量子霸权
S：一台通用量子计算机需要4000个逻辑量子比特，但目前的量子计算只有50~100个物理比特，所以你们的小量子计算机只能解决很小一部分经典计算机可以解决的问题。因此它也只能以加速器的形式出现，帮助经典计算机解决问题。但在解决一些问题上，比经典计算机快并不能够证明经典计算机不能解决这些问题，这里面还有一个需要证明经典计算机无法解决这些问题的理论问题。你们的第一个目标——量子霸权的实验，具体是如何展现量子芯片速度的霸权优势的？
Y：量子计算机在多项式时间内可以解决的问题类称为有界错误量子多项式时间复杂性类(Bounded-error Quantum Polynomial time, BQP)。而在证明P不等于NP之前，几乎没办法直接证明BQP严格真包含P（或者BPP2)。所以必须依赖一些复杂性的假设，比如之前计算机科学家设计的RSA加密就是依赖整数质因数分解十分困难的假设。但是Shor算法可以在多项式时间内解决整数质因数分解问题，所以整数质因数分解问题之前一直是量子计算超越经典计算所依赖的例子。但因为Shor算法（分解2048比特的整数）需要超过4000个逻辑量子比特去解决，所以近期大家没有继续试图使用Shor算法来展示量子霸权，而是试图用50~100个物理比特的机器产生一个非常大的概率分布3，然后证明这个概率分布在经典计算机上因为算力不够而无法产生。这个方案有两个好处，第一是其依赖的复杂性假设非常强，假设的是多项式时间层次(Polynomial Hierarchy, PH)从第三层开始不会坍缩。PH是计算机科学家认为极为不可能互相等价（即塌缩）的一个复杂性类层次，所以这个假设比整数分解的困难性假设更强。第二是这个方案对错误的容忍度比较强，不需要可容错的量子机器来实现，适合现阶段的NISQ系统。这里需要说明的是，（量子采样）这个计算任务本身是没有任何实用价值的，唯一的目的就是为量子计算机量身定制一类问题，展示其计算能力。
S：你这里还是有一个理论问题，因为需要证明这个分布无法用经典计算机产生。你们找到这样的例子了吗？
Y：理论上已经证明了这样的分布在量子世界里是无处不在的。50~100量子比特的量子态在哈尔测度(Haar measure)下必然会给出经典计算机模拟不了的概率分布（Porter-Thomas分布），所以现在实现量子霸权的方案之一是想用实验展示运行一段随机量子电路[5]，在实验噪声控制得当的情况下，产生一个有250~2100种不同输出结果的概率分布。而现今所有经典超级计算机都不可能从对输入的随机电路的描述中计算出整个输出的分布信息。
X：最近已经有一项结果证明了BQP真包含P，为什么不能直接应用在量子霸权的实验上？
Y：我想你说的是然·拉茨(Ran Raz)等人的工作[6]。虽然这项工作结论非常优美，但是不能帮助在实验上展示量子的加速，因为这个证明的方法是利用一个假想的运算能力强大的神谕 (oracle)，利用这个神谕，BQP和P这两个复杂性类可以相对区分开4，但这个神谕在现实中是不存在的。
Q：量子化学计算的目的就是求解电子态的薛定谔方程，而量子计算本身也遵从薛定谔方程，所以非常适合用来做量子化学模拟。然而模拟后，我们要对量子计算机得到的量子态进行一一测量，这样的测量是否和直接测量要模拟的量子系统（比如说氢原子）的复杂度一样大？是否只是相当于把测量对象从原来的系统替换成了人造的量子系统?
Y：这是一个很好的问题。量子计算机的优势就是可以精确地对量子态进行操作和运算，在量子计算机中把体系的全部信息读出来是不可能的，但是利用相位估计算法(phase estimation)[7]或者近期提出的VQE(Variational Quantum Eigensolver) 算法[8]可以读出很多有用的信息，比如基态的能量。而在原系统中我们是不能进行这样的操作的。
S：@Y你的第一个问题虽然是一个缩小的问题，但是从理论到实践是非常大的一步。首先，理论上证明不行的东西，在实际当中可能是可行的。理论只是说在问题大到一定程度的情况下，现在的机器会变得非常慢，以至于达到无法解决的程度。如果真找到了一个那么大的问题，这个问题在现有的量子计算机上又如何解决？要知道现在的量子计算机讨论的都是计算如何快，并没有讨论数据如何送上去。在实际中，量子计算机如何解决大数据的存储和传输问题？
Y：基于采样的量子霸权实验，这个问题的计算量非常大，但是问题的描述却十分简单，只需要包含一些量子门的电路图。量子计算机非常适合描述简单的问题，包括Shor算法解决的整数质因数分解问题、量子化学模拟都属于这类问题。在新兴的量子机器学习应用中，大数据的储存和传输就是很大的问题。现在量子科学家们正在积极寻找方法来解决这一瓶颈。
量子叠加态和量子通信
W：近来有人质疑量子计算机以及最近的量子通信实验都未真正实现量子纠缠和量子叠加态，这些质疑是否合理？
Y：对于判断量子叠加态和经典概率的区别，是有一个检验标准的，那就是贝尔不等式检验。贝尔不等式提出了一个可操作、可证伪的测试，具体形式是：|P(xz) – P(yz)| <= 1+ P(xy)，其中P(ab)为a、b事件同时发生的概率。任何没有量子特性的物理系统或者计算系统，是不能产生违背贝尔不等式的联合概率分布的。近期的量子计算实验以及量子通信实验均产生了违背贝尔不等式的概率分布[9,10]。
S：你说量子通信实验产生了违背贝尔不等式的概率分布。中国现在大幅报道的量子通信实际上不是在用量子做数据传输，而是用量子做密钥分发。这个量子分发也不是用于量子加密，而是利用量子特性使得如果发密钥时被截取或者监听，分发的双方立刻就会知道。这里有两个问题：(1)量子密钥分发是不是也产生了违背贝尔不等式的概率分布？(2)针对Shor算法的量子密码体系已经建立，也就是说，实际上量子计算已经放弃了在密码破解上的应用。如果是这样的话，量子密钥分发与（后）量子密码一点关系都没有了，只是在为经典密码学服务。那现在的经典密码密钥分发是如何进行的呢？量子密钥分发的意义是什么呢？
Y：你的理解是对的。量子密钥分发确实只是确保密钥的安全性。实际上最早的密钥分发协议BB84[11] (Charles Bennett, 1984)诞生于1984年，比Shor算法还要早十年。量子密钥分发基于纠缠态，所以肯定也可以产生违背贝尔不等式的概率分布，但是它利用的更多的是量子态的另外一个特性——不可克隆原理。不可克隆原理指出量子比特不能像经典比特一样随意地复制。每当一个量子被复制，原来的量子比特里的量子态必定被销毁，这是由量子理论的数学基础——线性代数决定的。不可克隆原理给量子计算带来了很多限制，但是IBM的查尔斯·本奈特(Charles Bennett)和吉勒斯·布拉萨德(Gilles Brassard)却敏锐地发现了这个特点，生成和保管密钥——每当有人窃听，密钥发送者和接收者就会察觉自己的密钥分发效率下降了。需要指出的一点是，量子密钥分发要求必须有一条经典通信通道，这条经典通道里的信息默认是公开的。
Y：我对现在的经典密码密钥分发的情况不了解。
X：@Y，你提到美国政府最近推出了一个开展量子计算和量子通信的国家计划。但里面没有提到量子密码密钥分发。这是为什么？
Y：是的，美国的计划里没有关于密码密钥分发的讨论。
量子霸权和量子计算机的结构
X：回到量子算法的讨论，最近有人提出了一些经典算法可以达到和量子算法同样的加速。这是否意味着量子计算和经典计算机相比已经没有加速了？
Y：最近埃文·唐(Ewin Tang)等人提出了新的经典算法来求解用户推荐问题[12]以及矩阵求逆问题[13]。他们的算法指数量级地缩短了求解的时间5，从复杂性角度上达到了和某类量子机器学习算法一样的速度，证明了量子算法在这些问题上没有优势。但是还有很多的量子算法与已知的经典算法相比有指数时间的优势，比如著名的Shor算法。埃文·唐的算法需要基于对输入矩阵的随机查询访问，而这类算法已经被证明（如果应用到整数质因数分解问题时）和Shor算法相比是有指数量级的差别的，所以新出现的算法在整数质因数分解等问题上是无望超过量子算法的。另外，新算法在解矩阵求逆问题上对于所求解的矩阵需要低秩等假设。新的经典算法虽然达到了同样的速度，但是它只能求解低秩的矩阵，而量子算法，例如HHL算法[14]，没有低秩这一要求。
S：在理论上微观粒子的叠加态是天然存在的一种状态。但在任何时刻的任何测量我们只能测到一种状态。那么叠加态是如何用到量子计算上的？
Q：是的，这些态不可能同时被测出来。当只有一个量子比特的时候，每一次测量只能测出一个具体的态，无所谓计算。但是当比特与比特间能耦合之后，我们在第一个量子比特进行输入，最后一个量子比特进行输出，中间过程不进行测量（当然这是个很简单理想化的理论模型），那么中间的量子比特就能同时以无数种状态的情况进行相互作用，从而实现量子计算。至于中间的态如何“同时存在于无数种状态中”，并不是关心的重点。
S：@Q，讲到这里，你最好还是把量子计算机的基本结构介绍一下。它还是图灵机吗？它还是冯·诺伊曼的结构吗？
Y：量子计算机基本结构称为量子图灵机，和NP图灵机非常相似，区别在于它可以有负的概率以及最后只能根据概率随机取出一个结果写入纸带。这个模型不太直观，所以不经常被提起。姚期智教授在1993年证明了量子图灵机和简单的量子线路模型等价[15]。现在基本可以认为量子计算机就是一个可逆逻辑电路加上一些特殊的量子门。和冯·诺伊曼结构相比，量子计算机是没有外部储存设备的，其CPU就是内存。可以认为量子计算机直接在内存里进行运算。
S：如果没有外存，现在的量子计算机的数据存储和输入输出是如何完成的呢？
Y：粗略地讲，可以把每个量子比特看作一个2个经典比特的内存空间。这和经典的内存的区别在于，多个内存组合不是简单地相加而是张量积。n个量子比特储存的是2n个经典比特的信息。在量子比特上进行量子门操作（物理上就是打激光、微波等操作）就等价于直接在内存空间里进行一个2n
S：那怎么解决呢，除了尽量减少I/O和在调度方面做一些重叠以外。
Y：慢常数倍的问题不需要解决，比如量子化学；慢指数倍的暂时还不知道如何解决：比如量子机器学习如何把用户数据以大矩阵的形式装进量子计算机。孙老师是I/O方面的专家，请问一般I/O方面的问题解决的思路是什么？
S：数据传输的速度是由慢的一方决定的。既然量子计算机的储存就是经典计算机的储存，那么量子计算机的I/O速度也取决于经典计算机的储存速度。对数据密集型的应用来说，这是一个非常要命的问题。现在经典计算机的内存比外存快400~4000倍。解决的方法有两点：局部性和并行性。并行性包括重叠技术，当然，我们有很多不同的方法用以增加数据的局部性和并行性。例如，利用数据的特性去设计数据结构以增强局部性。量子计算的数据有什么特性，我不知道。但是在结构上，量子计算机的内存没有分级存储器体系(memory hierarchy)，而分级存储是经典计算机的重要组成部分。
W：@S 听说你的研究小组今年（2018年）也申请到了一个大项目，是做I/O系统的研究。你能介绍一下吗？
S：是的，我们最近有一个美国科学基金委 (National Science Foundation, NSF) 的项目，是做I/O系统的开发。基本的想法是，从高性能计算的I/O软件栈出发，打通上面的内存层和下面的储存层，建造一个deep memory-storage hierarchy。
W：这个想法听起来很新颖。
S：我们这套系统有自己的理论和系统体系，但我们还是在经典计算机的框架下做的，与量子计算机没有交集。
总结
S：让我简单总结一下以上关于量子计算机的讨论：业界已经承认4000个逻辑量子比特（需要2亿物理量子比特支持）的通用量子计算机在短期内无法实现，现在的重点是实现/应用50~100个物理量子比特的量子计算机。也就是说，量子计算机只能解决一部分经典计算机能解决的问题。其应用与经典计算机结合，以加速器的形式出现。这样的应用在5~10年可以达到。因为这样的结合，并没有说量子计算机要做多少部分，也没有说量子计算机要做到多小。但另一方面，量子计算机的研究者“野心不死”，还要证明50~100个量子比特的量子计算机能达到量子霸权，也可以解决一些经典计算机解决不了的问题。理论上证明了这样的问题是存在的（虽然是一个人造的、不实际的问题）。但我认为，在现有的量子计算机上验证这个不实际的例子也不是一件容易的事，这包括现有量子计算机的硬件条件、软件条件和可能存在的I/O瓶颈。
Y：有一个小小的纠正，我们找的量子霸权的例子中没有I/O问题。
W：@Y是的，你们避开了I/O问题。但你们要在真实的机器上实现目标还是很困难的。从理论到实践是一大步，现在最大的IBM量子计算机只有50个物理比特，据说还不能同时使用。你们的困难很多呀。
Y：量子计算是有很多困难。但是摩尔定律已经走到尽头了，经典计算的加速也变得越来越困难了。
S： “摩尔定律已经走到尽头了”这句话已经说了二十多年了，但我并不认为摩尔定律在可见的十年之内会走到头。我在今年（2018年）10月举办的中国计算机大会(CNCC2018)的“CPU及xPU的未来之路”论坛上陈述了这一观点和论据。在那之后，英特尔公布了他们的摩尔定律。在可见的将来，英特尔依然会依照摩尔定律来发展芯片。
Y：从理论上来讲，摩尔定律总有一天会结束。从理论上讲，量子计算机代表了未来。
S：从理论上讲，理论和实践是一回事；但从实践上讲，理论和实践并不是一回事。理论和实践中间隔着一大步，有时是无法逾越的。但我还是希望你们成功。你们成功解决实际问题的那一天，也就是I/O变成量子计算瓶颈的那一天，也许那时我们就可以合作了。
Y：在可见的将来，量子计算是以加速器的形式出现的。经典计算的成功，也是量子计算的成功。我也真心希望你们的项目成功。
S：祝你们成功，祝我们成功，祝大家成功。新年快乐！
Q, S, W, X, Y：新年快乐！
作者介绍
孙贤和 2018CCF海外杰出贡献奖获得者。伊利诺理工大学(Illinois Institute of Technology)杰出教授(University Distinguished Professor)。IEEE Fellow，美国阿贡国家实验室(Argonne National Laboratory)客座教授和伊利诺理工大学可扩展计算软件实验室主任。主要研究方向为分布式计算理论等。sun@iit.edu |
脚注
1 肖尔时任贝尔实验室研究员，2003年加入MIT。
2 有界错误概率多项式时间复杂性类，Bounded-error Probabilistic Polynomial time。
3 即量子波色采样。
4 拉茨和塔尔(Tal)证明了如下结论：存在一个神谕O，使得BQPO
5 求解时间从ploy(n)下降到poly(log n)。
参考文献
[1] Lamar S. National Quantum Initiative Act[OL]. https://www.congress.gov/bill/115th-congress/house-bill/622
[2] Shor P. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J]. SIAM J.Sci.Statist.Comput,1994, 26(5):1484-1509.
[3] Regev O. On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. ACM Press, 2005: 84-93.
[4] Preskill J. Quantum computing in the era of NISQ[OL].(2018).
https://arxiv.org/abs/1801.00862.
[5] Boixo S, Isakov S V, Smelyanskiy V N , et al. Characterizing Quantum Supremacy in Near-Term Devices[J]. Nature Physics, 2016, 14(6).
[6] Raz R, Tal A. Oracle separation of BQP and PH[OL].(2018-05-31) https://eccc.weizmann.ac.il/report/2018/107/download/.
[7] Kitaev A, Shen A H, Vyalyi M N. Classical and quantum computation[M]. Amer Mathematical Society, 2002.
[8] Peruzzo A, Mcclean J R, Shadbolt P, et al. A variantional eigenvalue solver on a quantum processor[J]. Nature Communication, 2013, 5: 4213.
[9] Wang X L, Chen L K , Li W , et al . Experimental Ten-Photon Entanglement[J]. Physical Review Letters, 2016, 117(21):210502.
[10] Ren J G, Xu P, Yong H L, et al. Ground-to-satellite quantum teleportation[J]. Nature, 2017, 549: 70-73.
[11] Bennett C H, Brassard G. Quantum cryptography: Public key distribution and coin tossing[J]. Theoretical Computer Science, 1984, 560:175-179.
[12] Tang E. A quantum inspired classical algorithm for recommendation systems[OL]. (2018). https://arxiv.org/abs/1807.04271.
[13] Gilyen A, Lloyd S,Tang E. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension[OL].(2018). https://arxiv.org/abs/1811.04909.
[14] Harrow A W, Hassidim A, Lloyd S. Quantum algorihtm for solving linear systems of equations[OL].(2010). https://arxiv.org/abs/0811.3171
[15] Yao A. Quantum circuit complexity[C]// Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, 1993: 352-361.
附件
最简量子计算介绍
孙贤和
2018年1月11日
量子计算机是一个热门话题，经常被提起。在被人问了很多遍之后，我干脆把这个最简单的解释写下来与大家分享。
量子计算机有两个非常不一样的模型。一个是状态模型，一个是量子退火模型。量子计算基于量子比特(qubits)，理论证明通用量子计算需要至少4000个逻辑量子比特。根据第二种模型做的量子计算机现在已经实现，已有厂家（如D-Wave）在卖了。最新型的已经有2000个工作比特，已非常接近实用。但第二种模型只能做一种运算——模拟退火，并且不能证明比电子计算机快。用第一种模型做的量子计算机现在还都只有两位数量级的物理量子比特。要命的是，理论上已经证明如果要有4000个逻辑比特，按照第一种模型造的量子计算机需要有2亿个物理量子比特，那是一个无法达到的高度。
所以如果有人告诉你量子计算机会比电子计算机快1000倍，并且量子计算机很快就可以实用，你不能说他在骗你，但是他肯定是在忽悠你。最好的可能是在不久的将来，第一种量子计算可以作为电子计算机的加速器出现，在实际运算中得到应用。
除了制造的问题，量子计算现在的理论证明都没有把I/O算在里面。如果把I/O的开销算在里面，量子计算机并不比电子计算机快。I/O的问题是量子计算最重要的问题，比量子计算的算法还要重要。
量子计算投入小，曝光度高，所以大家都要做。但是大家还应当清楚地认识到量子计算离实际应用还有段距离。要真正取代电子计算机，只能说是有可能，但现在还看不到这种可能性。
中国计算机学会
微信号：ccfvoice
长按识别二维码关注我们
CCF推荐
【精品文章】
点击“阅读原文”，加入CCF。